package com.cn.codebrush.字符串;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author Boolean
 * @Date 2022/4/24 10:38
 * @Version 1.0
 */
public class No22括号生成 {
    public static void main(String[] args) {
        /**
         * n = 3
         * ["((()))","(()())","(())()","()(())","()()()"]
         * @param n
         * @return
         */
        System.out.println(generateParenthesis(1));
    }

    /**
     * 回溯法
     * AC
     * 注意和 三数之和、四数之和 的区别
     * dfs 左右两次
     */
    static List list = new ArrayList();
    public static List<String> generateParenthesis(int n) {
        generateParenthesisHelper(n,n,"");
        return list;
    }
    public static void generateParenthesisHelper(int l, int r, String curStr) {
        if(l == 0 && r == 0){
            list.add(curStr);
            return;
        }
        if(l<0 || r<0){
            return;
        }
        if(l > r){
            return;
        }
        generateParenthesisHelper(l-1,r,curStr+"(");
        generateParenthesisHelper(l,r-1,curStr+")");
    }

}
